线段树
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int a[N],n,m;
struct Node{
int l,r,sum,lenth,tag;
}tr[4*N];
void pushup(int x){
tr[x].sum = tr[tr[x].l].sum + tr[tr[x].r].sum;
return;
}
void buildtree(int x,int l,int r){
tr[x] = {l,r,0,r-l+1};
if(l == r){
tr[x].sum = a[l];
return;
}
buildtree(x<<1,l,l+r>>1);
buildtree(x<<1|1,(l+r>>1)+1,r);
pushup(x);
return;
}
void pushdown(int x){
if(!tr[x].tag) return;
tr[x<<1].tag += tr[x].tag;
tr[x<<1|1].tag += tr[x].tag;
tr[x<<1].sum += tr[x].tag * tr[x<<1].lenth;
tr[x<<1|1].sum += tr[x].tag * tr[x<<1|1].lenth;
tr[x].tag = 0;
return;
}
void change(int x,int l,int r,int v){
int ll = tr[x].l,rr = tr[x].r;
if(l <= ll && rr <= r){
tr[x].sum += v*tr[x].lenth;
tr[x].tag += v;
return;
}
if(rr<l || r < ll) return;
pushdown(x);
change(x<<1,l,r,v);
change(x<<1|1,l,r,v);
pushup(x);
return;
}
int query(int x,int l,int r){
int ll = tr[x].l,rr=tr[x].r;
if(l <= ll && rr <= r){
return tr[x].sum;
}
if(rr < l || r < ll) return 0;
pushdown(x);
return query(x<<1,l,r) + query(x<<1|1,l,r);
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
buildtree(1,1,n);
while(m--){
int opt,x,y,k;
cin>>opt;
if(opt == 1){
scanf("%lld%lld%lld",&x,&y,&k);
change(1,x,y,k);
}else{
scanf("%lld%lld",&x,&y);
printf("%lld\n",query(1,x,y));
}
}
return 0;
}板子板子板子
可持久化线段树
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N],n,m,tot;
int root[25*N]; //存各版本的root
struct Node{
int lc,rc,val; //lc,rc表示左右儿子索引
}tr[25*N];
int build(int l,int r){
int now = ++tot; //申请一个新编号
if(l == r){
tr[now].val = a[l];
return now;
}
int mid = l+r>>1;
tr[now].lc = build(l,mid);
tr[now].rc = build(mid+1,r);
return now; //回传当前节点编号
}
int clone(int old){ // 复制节点
tr[++tot] = tr[old];
return tot; // 返回节点编号
}
int update(int old,int l ,int r,int pos,int val){
int now = clone(old); // 复制节点
if(l == r){
tr[now].val = val;
return now;
}
int mid = l+r>>1;
if(pos <= mid){
tr[now].lc = update(tr[now].lc,l,mid,pos,val); // 修改左儿子
}else{
tr[now].rc = update(tr[now].rc,mid+1,r,pos,val);//同上
}
return now; // 返回节点编号
}
int query(int now,int l,int r,int pos){ //Query没什么变化
if(l == r)
return tr[now].val;
int mid = l+r>>1;
if(pos <= mid){
return query(tr[now].lc,l,mid,pos);
}else{
return query(tr[now].rc,mid+1,r,pos);
}
}
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
root[0] = build(1,n);
int cnt = 0;//存root 编号
while(m--){
int v,opt;
scanf("%d%d",&v,&opt);
if(opt == 1){
int pos,val;scanf("%d%d",&pos,&val);
root[++cnt] = update(root[v],1,n,pos,val);
}else{
int pos;scanf("%d",&pos);
printf("%d\n",query(root[v],1,n,pos));
root[++cnt] = root[v];
}
}
return 0;
}区别在动态开点，不算太难，空间要开25N，long long看数据范围
FHQ平衡树
核心是split和merge，比起带旋平衡树更好写，常数更优秀，可拓展性强，并且是可持久化平衡树的基础
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
int n,tot,root;
struct Node{
int l,r,val,prio;
int sz;
}tr[N];
int new_node(int val){
tr[++tot] = {0,0,val,rand(),1};
return tot;
}
void pushup(int x){
tr[x].sz = tr[tr[x].l].sz + tr[tr[x].r].sz +1;
}
void split(int now,int val,int &x,int &y){
if(!now) {x = y = 0; return;}
if(tr[now].val <= val){
x = now;
split(tr[now].r,val,tr[now].r,y);
}else{
y = now;
split(tr[now].l,val,x,tr[now].l);
}
pushup(now);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(tr[x].prio > tr[y].prio){
tr[x].r = merge(tr[x].r,y);
pushup(x);
return x;
}else{
tr[y].l = merge(x,tr[y].l);
pushup(y);
return y;
}
}
void insert(int v){
int x,y;
split(root,v,x,y);
root = merge(merge(x,new_node(v)),y);
}
void erase(int v){
int x,y,z;
split(root,v,x,y);
split(x,v-1,x,z);
if(z) z = merge(tr[z].l,tr[z].r);
root = merge(merge(x,z),y);
}
int get_low(int v){
int x,y;
split(root,v-1,x,y);
int ans = tr[x].sz +1;
root = merge(x,y);
return ans;
}
int rank_val(int now,int rk){
if(tr[tr[now].l].sz >= rk){
return rank_val(tr[now].l,rk);
}else if(tr[tr[now].l].sz +1 == rk){
return tr[now].val;
}else{
return rank_val(tr[now].r,rk-tr[tr[now].l].sz -1);
}
}
int get_pre(int v){
int x,y;
split(root,v-1,x,y);
int ans = rank_val(x,tr[x].sz);
root = merge(x,y);
return ans;
}
int get_nxt(int v){
int x,y;
split(root,v,x,y);
int ans = rank_val(y,1);
root = merge(x,y);
return ans;
}
int main(){
scanf("%d",&n);
while(n--){
int opt,x;
scanf("%d%d",&opt,&x);
opt==1?(insert(x),0):opt==2 ? (erase(x),0) :
opt==3?(printf("%d\n",get_low(x)),0):
opt==4 ? (printf("%d\n", rank_val(root,x)),0) :
opt==5 ? (printf("%d\n", get_pre(x)),0) :
(printf("%d\n", get_nxt(x)),0);
}
return 0;
}坑点：
- new_node要数据要传完！
- 记得pushup
- split后记得更新root为新的merge后的结果
可持久化平衡树
基于FHQ（因为FHQ不修改树的结构）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 4e7+5;
int n,tot;
vector<int>roots;
struct Node{
int l,r,val,prio;
int sz;
}tr[N];
int new_node(int val){
tr[++tot] = {0,0,val,rand(),1};
return tot;
}
int clone(int now){ //复制节点
tr[++tot] = tr[now];
return tot;
}
void pushup(int x){
tr[x].sz = tr[tr[x].l].sz + tr[tr[x].r].sz +1;
}
void split(int now,int val,int &x,int &y){
if(!now) {x = y = 0; return;}
int new_now = clone(now);//复制now节点
if(tr[now].val <= val){
x = new_now;
split(tr[now].r,val,tr[new_now].r,y); //递归处理原节点的儿子
}else{
y = new_now;
split(tr[now].l,val,x,tr[new_now].l);
}
pushup(new_now);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(tr[x].prio > tr[y].prio){
int new_x = clone(x);
tr[new_x].r = merge(tr[x].r,y);
pushup(new_x);
return new_x;
}else{
int new_y = clone(y);
tr[new_y].l = merge(x,tr[y].l);
pushup(new_y);
return new_y;
}
}
int insert(int root,int v){
int x,y;
split(root,v,x,y);
return merge(merge(x,new_node(v)),y);
}
int erase(int root,int v){
int x,y,z;
split(root,v,x,y);
split(x,v-1,x,z);
if(z) z = merge(tr[z].l,tr[z].r);
return merge(merge(x,z),y);
}
int get_low(int root,int v){//因为不能直接split&merge，所以改为只读遍历
int cnt = 0;
while(root){
if(tr[root].val < v){
cnt += tr[tr[root].l].sz +1;
root = tr[root].r;
} else{
root = tr[root].l;
}
}
return cnt+1;
}
int rank_val(int root,int rk){
while(root){
if(tr[tr[root].l].sz >= rk){
root = tr[root].l;
}else if(tr[tr[root].l].sz == rk-1){
return tr[root].val;
}else{
rk -= tr[tr[root].l].sz +1;
root = tr[root].r;
}
}
return -1;
}
int get_pre(int root,int v){
int ans = -1*(int)(1e9)+5;
while(root){
if(tr[root].val < v){
ans = max(ans,tr[root].val);
root = tr[root].r;
}else root = tr[root].l;
}
return ans;
}
int get_nxt(int root,int v){
int ans = (int)(1e9)+5;
while(root){
if(tr[root].val > v){
ans = min(ans,tr[root].val);
root = tr[root].l;
}else{
root = tr[root].r;
}
}
return ans;
}
int main(){
scanf("%d",&n);
roots.reserve(n+1);
roots.push_back(0);
while(n--){
int v,opt,x;
scanf("%d%d%d",&v,&opt,&x);
int cur = roots[v];
if(opt == 1){
int new_root = insert(cur,x);
roots.push_back(new_root);
}else if(opt == 2){
int nr = erase(cur,x);
roots.push_back(nr);
}else if(opt == 3){
printf("%d\n",get_low(cur,x));
roots.push_back(cur);
}else if(opt == 4){
printf("%d\n",rank_val(cur,x));
roots.push_back(cur);
}else if(opt == 5){
printf("%d\n",get_pre(cur,x));
roots.push_back(cur);
}else{
printf("%d\n",get_nxt(cur,x));
roots.push_back(cur);
}
}
return 0;
}相对比较细小（？）